/*
Benchmark  the std::partial_sort() function

Author: Jyrki Katajainen
Email: jyrki@diku.dk
$Revision: 1.1 $
$Date: 2005/01/26 11:58:11 $

*/

#include <algorithm> // defines std::partial_sort
#include "input_generation.c++" // defines random_sequence()
#include "do_nothing.c++" // defines do_nothing()

template <
  typename element, 
  typename ordering,
  typename container,
  typename position
>
class experiment {
public:
  experiment(unsigned int n) : n(n) {
    a = container(n, element());
    less = ordering();
  }
  void primal() {
    random_sequence(a.begin(), a.end());
    std::partial_sort(a.begin(), a.end(), a.end(), less);
  }
  void dual() {
    random_sequence(a.begin(), a.end());
    do_nothing<void, position, position, position, ordering>(a.begin(), a.end(), a.end(), less);
  }
private:
  unsigned int n;
  container a;
  ordering less;
};

